package com.lsa.shenn.common.perm;

public class SubsetEnumerator
{
	private final int sizeOfSet;
	private final int sizeOfSubset;
	
	public SubsetEnumerator(int sizeOfSet, int sizeOfSubset)
	{
		this.sizeOfSet = sizeOfSet;
		this.sizeOfSubset = sizeOfSubset;
	}
	
	public int[] firstSet()
	{
		int[] set = new int[this.sizeOfSet];
		
		for (int i = 0; i < this.sizeOfSet - this.sizeOfSubset; i++)
		{
			set[i] = 0;
		}
		
		for (int i = this.sizeOfSet - this.sizeOfSubset; i < this.sizeOfSet; i++)
		{
			set[i] = 1;
		}
				
		return set;
	}
	
	public int[] nextSet(int[] set)
	{
		if (set == null)
		{
			return firstSet();
		}
		
		int i = set.length - 2;
		while(i > -1 && !(set[i] == 0 && set[i+1] == 1))
		{
			--i;
		}
		
		if (i < 0)
		{
			return null;
		}
		
		int s = i;
		
		int unitNumber = 1;
		
		for (int j = s+2; j < set.length; ++j)
		{
			if (set[j] == 1)
			{
				++unitNumber;
			}
		}
		
		set[s] = 1; // length - s + 1
		
		for(int j = s+1; j < set.length - unitNumber + 1; ++j)
		{
			set[j] = 0;
		}
		
		for(int j = set.length - unitNumber + 1; j < set.length; ++j)
		{
			set[j] = 1;
		}
		
		return set;
	}
}
